package com.kitty.record.kittyalgorithm.audition;

import java.util.HashSet;
import java.util.Set;

/**
 * 有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。
 * 示例1:
 * 输入：S = "qqe"
 * 输出：["eqq","qeq","qqe"]
 * 示例2:
 * 输入：S = "ab"
 * 输出：["ab", "ba"]
 * 提示:
 * 字符都是英文字母。
 * 字符串长度在[1, 9]之间。
 * //todo 这个理解起来比较难
 *
 * @Author SHEN
 * @Date 2020/11/26
 */
public class LeetCode0808 {


    public static void main(String[] args) {
        String s = "efg";
        String[] res = permutation(s);
        for (String re : res) {
            System.out.println(re);
        }
    }


    public static String[] permutation(String S) {
        Set<String> res = new HashSet<>();
        StringBuilder sb = new StringBuilder();
        boolean[] marks = new boolean[S.length()];
        backtracking(res, S, sb,marks);
        return res.toArray(new String[res.size()]);
    }

    private static void backtracking(Set<String> res, String s, StringBuilder sb, boolean[] marks) {
        if (sb.length() == s.length()) {
            res.add(sb.toString());
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            if(!marks[i]){
                marks[i] = true;
                sb.append(s.charAt(i));
                backtracking(res, s, sb,marks);
                sb.deleteCharAt(sb.length()-1);
                marks[i] = false;
            }

        }

    }
}
